package library;

import java.util.Arrays;
import java.util.Scanner;

/**
 * This is a complete program that determines the number of ways to make a given amount of money using unlimited amounts of a fixed number of coins 
 * @author ekulcyk
 *
 */
public class Coins {

	//The value of each coin, from highest to lowest
	int[]values = {50,25,10,5,1};
	//The maximum values you will be asked to solve
	int maxValue = 7489;

	long sol[][];

	public Coins() {
		Scanner s = new Scanner(System.in);

		sol = new long[values.length][maxValue+1];
		
		for(long[] a: sol)
			Arrays.fill(a, -1);
		
		for(int i =0; i <=maxValue; i++){
			solve(i,0);
		}
		
		while(s.hasNext()){
			System.out.println(sol[s.nextInt()][0]);
		}
	}

	public long solve(int amount, int last){
		if(amount==0)
			return 1;
		if(last==values.length)
			return 0;

		if(sol[last][amount]!=-1)
			return sol[last][amount];

		long tot = solve(amount,last+1);
		if(values[last]<=amount)
			tot+=solve(amount-values[last],last);

		sol[last][amount] = tot;
		return sol[last][amount];
	}

	public static void main(String[] args) {
		new Coins();
	}
}
